package com.gali.leetcode.day6;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

/**
 * @Auther: gali
 * @Date: 2022-07-19 20:21
 * @Description:电话号码的字母组合：利用回溯
 */
public class Solution {
    List<String> list = new ArrayList<>();
    public List<String> letterCombinations(String digits) {
        int length = digits.length();
        //特殊情况
        if (length==0||digits==""){
            return list;
        }
        //存储数据
        HashMap<Character, String[]> map = new HashMap<>();
        map.put('2', new String[]{"a","b","c"});
        map.put('3', new String[]{"d","e","f"});
        map.put('4', new String[]{"g","h","i"});
        map.put('5', new String[]{"j","k","l"});
        map.put('6', new String[]{"m","n","o"});
        map.put('7', new String[]{"p","q","r","s"});
        map.put('8', new String[]{"t","u","v"});
        map.put('9', new String[]{"w","x","y","z"});
        findCombinations(digits, 0, "", map);
        return list;
    }
    //回溯
    private void findCombinations(String digits,int index,String tem,HashMap<Character, String[]> map){
        if (tem.length()==digits.length()){
            list.add(tem);
            return;
        }
        for (int i = 0; i < map.get(digits.charAt(index)).length; i++) {
            findCombinations(digits,index+1,tem+map.get(digits.charAt(index))[i],map);
        }
    }

    //四数之和---排序+双指针
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> lists=new ArrayList<>();
        int length = nums.length;
        //特殊情况
        if (nums==null||length<4){
            return lists;
        }
        Arrays.sort(nums);//排序
        for (int i = 0; i < length-3; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            //防止三数相加超过int的界限
            if ((long) nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
                break;
            }
            if ((long)nums[i] + nums[length - 3] + nums[length - 2] + nums[length - 1] < target) {
                continue;
            }
            for (int j = i + 1; j < length - 2; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                if ((long) nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {
                    break;
                }
                if ((long)nums[i] + nums[j] + nums[length - 2] + nums[length - 1] < target) {
                    continue;
                }
                int left = j + 1, right = length - 1;
                while (left < right) {
                    int sum = nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum == target) {
                        //将数组转化为list对象
                        lists.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        //去重
                        while (left < right && nums[left] == nums[left + 1]) {
                            left++;
                        }
                        left++;
                        while (left < right && nums[right] == nums[right - 1]) {
                            right--;
                        }
                        right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        right--;
                    }
                }
            }
        }
        return lists;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        List<String> strings = solution.letterCombinations("23");
        System.out.println(strings);
    }
}
